import javax.swing.JLabel;
//MERGE SORT WITHOUT RECURSION
//Recursion can be very memory demanding. Without recursion:
//First loop: Sort every element (1 element sorted lists) by swapping 
//with its neighbour (1) element (sorted list) if it is bigger. 2'nd
//loop merge every 2 element sorted lists with their 2 element sorted
//lists neighbours. 3'rd loop we merge the 3 element sorted lists ...
//Worst, Average & Best: O(nlogn)
class MergeSort<T extends Comparable<T>> extends SortAlgorithm<T> { 
    MergeSort(JLabel listLabel, JLabel timeLabel, JLabel averageTimeLabel, JLabel statusLabel) { 
        super(listLabel, timeLabel, averageTimeLabel, statusLabel);
    }
    
    @Override
    protected void sort() { 
        int start1, start2, end1, end2, i1, i2, k;
        int N = m_list.size();
        Comparable[] ak = new Comparable[N];
        int subSize = 1;
        while (subSize < N) {
            for (start1 = 0; start1 < N; start1 += subSize*2) {
                start2 = start1 + subSize;
                end1 = java.lang.Math.min(start2 - 1, N-1);
                end2 = java.lang.Math.min(end1+subSize, N-1);
                i1 = start1;  
                i2 = start2;
                k = 0;
                while ((i1 <= end1)&&(i2 <= end2)) {
                    if (less(i1, i2)) { ak[k] = m_list.get(i1); i1++; 
                    } else { ak[k] = m_list.get(i2); i2++; }
                    k++;
                }
                if (k < subSize*2) {
                    while (i1 <= end1) { ak[k]=m_list.get(i1); i1++; k++; }
                    while (i2 <= end2) { ak[k]=m_list.get(i2); i2++; k++; }
                }
                k = 0;
                for (int i = start1; i <= end2; i++) { m_list.set(i, (T)ak[k]); k++; }
            }
            subSize *= 2;
        }
    }
}
